import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-11-09
 * Time: 17:12
 */
//动态规划分析：
//    1.问题：求从三角形顶部到底部的最小路径和
//    2.状态定义：转化为子问题就是求第一行第一个元素到第i行第j列元素的最短路径之和
//    3.状态转移方程：这里三角矩阵是一个二维数组，那么需要构造一个新的嵌套顺序表将给定的顺序表加入到其中，这里我们可以采取从下往上的方法来做，将最后一行元素作为初始值
//                  那么到第i行第j列的最短路径就是先求出第i+1行，第j列和第i+1行，第j+1列的最小值，再加上第i行第j列这个元素本身
//    4.转态初始值：最后一行元素
//    5.返回值：求出新的顺序表中第一行第一个元素的大小即为最短路径之和
public class ShortesPath {
    public static int minimumTotal(ArrayList<ArrayList<Integer>> triangle){
       if(triangle.isEmpty()){
           return 0;//如果三角形矩阵为空，那么直接返回0；
       }
       ArrayList<ArrayList<Integer>> minsum=new ArrayList<>(triangle);//建立新的嵌套顺序表存储矩阵中到达每个元素的最短路径之和
       int row=minsum.size();//行数为链表的长度
       int curnum=0;//存储到达每个元素的最短路径之和
       for(int i=row-2;i>=0;i--){//从下往上计算，那么初始值就是最后一行元素的大小，所以直接从倒数第二行开始计算
           for(int j=0;j<=i;j++){
                curnum=Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j+1))+triangle.get(i).get(j);//每个最短路径之和就是由下一行的相邻元素的最小值，再加上这个元素
                minsum.get(i).set(j,curnum);//把从triangle求出的每一个minnum值放到新的minsum顺序表中
           }
       }
       return minsum.get(0).get(0);//最后算的第一行的第一个元素就是最短路径之和
    }
}
